package E_2024;

import java.util.Arrays;

/*
题目描述
    祖国西北部有一片大片荒地，其中零星的分布着一些湖泊，保护区，
    矿区整体上常年光照良好，但是也有一些地区光照不太好某电力公司希望在这里建设多个光伏电站，
    生产清洁能源对每平方公里的土地进行了发电评估，其中不能建设的区域发电量为0kw，
    可以发电的区域根据光照，地形等给出了每平方公里年发电量x千瓦我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益。
输入描述
    第一行输入为调研的地区长，宽，以及准备建设的电站 [长宽相等，为正方形] 的边长
    最低要求的发电量之后每行为调研区域每平方公里的发电量
输出描述
    输出为这样的区域有多少个
示例1
    输入：
    2 5 2 6
    1 3 4 5 8
    2 3 6 7 1
    输出：
    4
    说明：
    输入长为2，宽为5的场地，建设的场地为正方形场地，边长为2，要求场地的发电量大于等于6
示例2
    输入：
    2 5 1 6
    1 3 4 5 8
    2 3 6 7 1
    输出：
    3
    说明：
    输入长为2，宽为5的场地，建设的场地为正方形场地，边长为1，要求场地的发电量大于等于6
示例3
    输入：
    2 5 1 0
    1 3 4 5 8
    2 3 6 7 1
    输出：
    10
    说明：
    输入长为2，宽为5的场地，建设的场地为正方形场地，边长为1，要求场地的发电量大于等于0即可
    https://pic2.zhimg.com/v2-5c324653ebca57f30d30ef33bfaefe1b_1440w.jpg
 */
public class E_200_14 {
    public static void main(String[] args) {
        System.out.println(ans(new int[][]{{1,3,4,5,8},{2,3,6,7,1}}, 1 ,0));
        System.out.println(ans(new int[][]{{1,3,4,5,8},{2,3,6,7,1}}, 1 ,6));
        System.out.println(ans(new int[][]{{1,3,4,5,8},{2,3,6,7,1}}, 2 ,6));
    }
    public static int ans(int[][] arr, int length, int sum){
        // 计算前缀累计和
        int[][] temp = new int[arr.length + 1][arr[0].length];
        for (int i = 1; i <= arr.length; i++) {
            for (int l = 0; l < arr[0].length; l++) {
                temp[i][l] = i == 1 ? arr[i-1][l] : arr[i-1][l] + temp[i-1][l];
            }
        }
        for (int[] ints : temp) {
            System.out.println(Arrays.toString(ints));
        }
        // 起始行为边长
        int hig = length;
        int ans = 0;
        while (hig <= arr.length){
            int num = 0;
            for (int i = 0; i < arr[0].length; i++) {
                // 计算宽达到边长后，当前宽值 - 超出宽的值
                if (i >= length)
                    num = num - temp[hig][i-length] + temp[hig-length][i-length];
                // 边长累积和为 当前行值 - 超出边长的值
                num += temp[hig][i] - temp[hig-length][i];
                if (num >= sum) ans++;
            }
            hig++;
        }
        return ans;
    }
}
